package com.goudan.practice.math;

/**
 * 统计素数 个数
 * 素数： 只能被1和自身整除的自然数，0、1 除外
 * 埃筛法
 * 输入100 输出 25
 */
public class PrimeNumber {

    public static void main(String[] args) {
        int con = bf(100);
        System.out.println(con);
    }

    /**
     * 埃筛法
     */
    public static int eratosthenes(int n) {

        return 0;
    }




    /**
     * 暴力算法
     */
    public static int bf(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            count += isPrime(i) ? 1 : 0;
        }
        return count;
    }

    /**
     * 判断是否是素数
     * i < x 可以优化为 i < Math.sqrt(x)
     */
    private static boolean isPrime(int x) {
        for (int i = 2; i < x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

}
